package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author rkc
 * @date 2022/9/16 13:59
 */
public class LC57插入区间 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int k = 0;
        while (k < intervals.length && intervals[k][1] < newInterval[0]) ans.add(intervals[k++]);
        if (k < intervals.length) {
            newInterval[0] = Math.min(newInterval[0], intervals[k][0]);
            while (k < intervals.length && intervals[k][0] <= newInterval[1]) newInterval[1] = Math.max(newInterval[1], intervals[k++][1]);
        }
        ans.add(newInterval);
        while (k < intervals.length) ans.add(intervals[k++]);
        return ans.toArray(new int[ans.size()][]);
    }
}
